Genomgång av dugga 2024

1.

Skriv påståendena "Alla Volvo är röda" och "Det finns röda BMW" på predikatlogisk form. Glöm inte att definiera lämpligt universum.

Varför är universum viktigt?
Ett predikat är en funktion och funktioner behöver en definitionsmängd

Lösning

Sätt $u = "alla bilar"$

Definiera, för $x \in u$ :
$V (x) : x är en Volvo$
$B (x) : x är en BMW$
$R (x) : x är röd$

$\forall x \in u : V (x) ⟹ R (x)$
$\exists x \in u : B (x) \land R (x)$

2.

Definiera en talföljd $F (n), n \geq 1$ ett heltal, genom

\begin{cases}
F(1)=1\
F(n)=(2n-1)F(n-1),\enspace n\geq2
\end

> V i s a a t t, f ö r a l l a h e l t a l $ n \geq 1 $, > $ $ F (n) = \frac{(2 n)!}{2^{n} n!}

Lösning

Tip från Pierre

Tänk igenom vilken metod man ska använda för att lösa en uppgift innan man börjar räkna så kör man inte fast i något hörn.

Induktionsbevis:

Basfallet: $n = 1 : F (1) = 1, \frac{(2 * 1)!}{2^{1} 1!} = 1$
Basfallet gäller

Antag att påståendet gäller för något $m$
Betrakta påståendet $m + 1$ :

$F (m + 1) = (2 (m + 1) - 1) F ((m + 1) - 1)$
$= (2 m + 2 - 1) F (m)$
$= (2 m + 1) F (m)$

$Induktionsantagande = (2 m + 1) \frac{(2 m)!}{2^{m} m!} = \frac{(2 m + 1)!}{2^{m} m!}$

Har $F (m + 1) = \frac{(2 m + 1)!}{2^{m} m!} = \frac{2 (m + 1)}{2 (m + 1)} \cdot \frac{(2 m + 1)!}{2^{m} m!} = \frac{(2 m + 2)!}{2^{m + 1} (m + 1)!} = \frac{(2 (m + 1))!}{2^{m + 1} (m + 1)!}$

Från induktionsprincipen fås att $F (n) = \frac{(2 n)!}{2^{n} n!} \forall n \geq 1$

3.

Rita två grafer som bägge har 5 noder, innehåller minst en triangel (en cykel med längd 3) men ej är isomorfa. Motivera varför de ej är isomorfa.

Det är inte nödvändigt att bevisa att det inte finns en bijektion.

Exempelvis:
I den ena grafen har jag två noder som som inte är sammankopplade till triangeln men i den andra är de kopplade.

4.

Fem punkter finns utplacerade inuti en kvadrat med sidlängd 2. Visa att det alltid går att välja två av dessa punkter så att avståndet mellan dem inte överstrider $\sqrt{2}$ .

Lösning

Dela in kvadraten i fyra kvadrater.

Lådprinciper medför att det finns minst en "del" med minst 2 punkter

Längsta avståndet mellan två punkter i en del är diagonalen, med längden $\sqrt{2}$ .

5.

För två mängder $S_{1}$ och $S_{2}$ , antag att $R_{1}$ är en partiell ordning på $S_{1}$ och $R_{2}$ en partiell ordning på $S_{2}$ . Definiera en ny relation $R$ på $S_{1} \times S_{2}$ enligt att $(a_{1}, a_{2}) R (b_{1}, b_{2})$ om och endast om något av följande gäller:

i) $a_{1} \neq b_{1}$ och $a_{1} R_{1} b_{1}$ , eller
ii) $a_{1} = b_{1}$ och $a_{2} R_{2} b_{2}$ .

Visa att $R$ är en partiell ordning på $S_{1} \times S_{2}$ .

Lösning

Om $R$ är reflexiv, antisymmetrisk och transitiv är den en partiell ordning på $S_{1} \times S_{2}$ .

Reflexiv

Tag $(a_{1}, a_{2}) \in S_{1} \times S_{2}$ . Vill visa $(a_{1}, a_{2}) R (a_{1}, a_{2})$

Eftersom $R_{1}$ och $R_{2}$ både är reflexiva, gäller $a_{1} R_{1} a_{1}$ och $a_{2} R_{2} a_{2}$ .

$a_{1} = a_{1} \land a_{2} R_{2} a_{2}$ är alltid sant.

Antisymmetrisk

Tag $(a_{1}, a_{2}), (b_{1}, b_{2}) \in S_{1} \times S_{2}$
Vill visa $(a_{1}, a_{2}) R (b_{1}, b_{2}) \land (b_{1}, b_{2}) R (a_{1}, a_{2}) ⟹ (a_{1}, a_{2}) = (b_{1}, b_{2})$

Antag att $(a_{1}, a_{2}) R (b_{1}, b_{2}) \land (b_{1}, b_{2}) R (a_{1}, a_{2})$

Antag också att $a_{1} \neq b_{1}$ . Från definitionen av $R$ har vi då:

$(a_{1}, a_{2}) R (b_{1}, b_{2}) ⟹ a_{1} R_{1} b_{1}$
$(b_{1}, b_{2}) R (a_{1}, a_{2}) ⟹ b_{1} R_{1} a_{1}$

$R_{1}$ är antisymmetrisk vilket medför att $a_{1} = b_{1}$ . Motsägelse

$a_{1} = b_{1}$ måste vara sant

Från definitionen av $R$ fås då:

$(a_{1}, a_{2}) R (b_{1}, b_{2}) ⟹ a_{2} R_{2} b_{2}$
$(b_{1}, b_{2}) R (a_{1}, a_{2}) ⟹ b_{2} R_{2} a_{2}$

$R_{2}$ är antisymmetrisk vilket medför att $a_{2} = b_{2}$

$(a_{1}, a_{2}) R (b_{1}, b_{2}) \land (b_{1}, b_{2}) R (a_{1}, a_{2}) ⟹ a_{1} = b_{1}, a_{2} = b_{2} ⟺ (a_{1}, a_{2}) = (b_{1}, b_{2})$

D.v.s. $R$ är antisymmetrisk VSV.

Transitiv

Tag $(a_{1}, a_{2}), (b_{1}, b_{2}), (c_{1}, c_{2}) \in S_{1} \times S_{2}$

Vill visa att $(a_{1}, a_{2}) R (b_{1}, b_{2}) \land (b_{1}, b_{2}) R (c_{1}, c_{2}) ⟹ (a_{1}, a_{2}) R (c_{1}, c_{2})$

Antag $(a_{1}, a_{2}) R (b_{1}, b_{2}) \land (b_{1}, b_{2}) R (c_{1}, c_{2})$ , från det fås att $a_{1} R_{1} b_{1} \land b_{1} R_{1} c_{1}$

$R_{1}$ transitiv $⟹ a_{1} R_{1} c_{1}$

Om $a_{1} \neq c_{1}$ ger $a_{1} R_{1} c_{1}$ direkt att $(a_{1}, a_{2}) R (c_{1}, c_{2})$ p.g.a. i).

Antag att $a_{1} = c_{1}$

Från antisymmetri hos $R_{1}$ fås att $a_{1} = b_{1}$ (vi har $a_{1} R_{1} b_{1}$ och $b_{1} R_{1} c_{1}$ , $a_{1} = c_{1}$ )

$(a_{1} = b_{1} = c_{1})$ . Från definitionen av $R$ fås då $a_{2} R_{2} b_{2}$ Dvs, $(b_{1}, b_{2}) R (c_{1}, c_{2}) \land b_{1} = c_{1}$
$⟹ b_{2} R_{2} c_{2}$ från ii).

$R_{2}$ transitiv medför att $a_{2} R_{2} c_{2}$
Det medför att $R$ är transitiv VSV.

$R$ reflexiv, antisymmetrisk och transitiv vilket innebär att den är en partiell ordning på $S_{1} \times S_{2}$ .